package com.robert.BCH;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class bchDecode {
    //在这里给出计算syndrome的函数、矩阵求逆以及判断矩阵是否为0的函数
    //最终给出解码函数
    //下面的函数出了decode，其他的设置为private，如果有需要设置成public即可调用

    /**
     * BCH解码
     * @param codeword 需要解码的码字
     * @param iPoly 选择的第i个多项式
     * @param p 公共参数
     * @param pc 预计算参数
     * @return 返回正确的消息
     * @throws Exception 抛出异常
     */
    public int[] decode(int[] codeword, int iPoly, parameters p,preCompute pc) throws Exception{
        int[][] s = computeSyndrome(codeword,pc,p,iPoly);
        int[] is = indexSyndromes(s,pc,p);
        int v = lengthOfNonZeroMatrix((pc.getDistGen()[iPoly]-1)/2,p,pc,is);
        List<Integer> err = findError(s,is,v,p,pc);
        int[] code = getCorrectCodeword(codeword,err);
        polynomial msg = new polynomial(code).divide(pc.getGenPoly()[iPoly]);
        return msg.getNums();
    }

    /**
     * 验证是否解码成功
     * @param msg1 正确的消息
     * @param msg2 解码后的消息
     * @return 如果解码正确则返回true，否则返回false
     */
    public boolean isCorrect(int[] msg1,int[] msg2){
        for(int i=0;i<msg1.length;i++){
            if(msg1[i]!=msg2[i]) return false;
        }
        return true;
    }

    public int[] disturbCodeword(int[] codeword,parameters p, preCompute pc,int iPoly){
        int maxErr = (pc.getDistGen()[iPoly]-1)/2;
        Random rand = new Random();
        int ne = rand.nextInt(maxErr)+1;
        for(int i=0;i<ne;i++){
            int index = rand.nextInt(p.getN());
            codeword[index] = (codeword[index]+1)%2;
        }
        return codeword;
    }

    /**
     * 计算syndromes
     * @param codeword 要解码的01数组
     * @param pc 预计算参数
     * @param p 公共参数
     * @param iPoly 选择的第i个多项式
     * @return 返回syndromes
     */
    private int[][] computeSyndrome(int[] codeword, preCompute pc, parameters p, int iPoly){
        int d = pc.getDistGen()[iPoly];
        int[][] syndrome = new int[d-1][p.getG().getDeg()-1];
        for(int i=0;i<d-1;i++){//计算d-1个syndrome
            polynomial tSyndrome = new polynomial("0");
            //把alpha带入多项式里，需要更新一下指数部分，然后求和
            for(int j=0;j<p.getN();j++){
                if(codeword[j]!=0){
                    int index = Math.floorMod((codeword.length-1-j)*(i+1)-1,p.getN());
                    int[] aik = pc.getAlpha().getValue()[index];
                    tSyndrome = tSyndrome.add(new polynomial(aik));
                }
            }
            syndrome[i] = tSyndrome.extend(p.getG().getDeg()-1-tSyndrome.getDeg());
        }
        return syndrome;
    }

    /**
     * 把syndrome转成alpha的幂次形式
     * @param syndromes syndrome
     * @param pc 计算后的参数
     * @param p 公共参数
     * @return syndrome的幂次形式
     */
    private int[] indexSyndromes(int[][] syndromes, preCompute pc, parameters p){
        int[] indexSyn = new int[syndromes.length];
        for(int i=0;i< syndromes.length;i++){
            int[] si = syndromes[i];
            int decSi = 0;
            int twos = 1;
            for(int j=si.length-1;j>=0;j--){
                if(si[j]==1) decSi += twos;
                twos *= 2;
            }
            if(decSi!=0){
                int index = Math.floorMod(decSi-1,p.getN());
                indexSyn[i] = pc.getAlpha().getIndexes()[index];
            }
        }
        return indexSyn;
    }

    /**
     * 找到一个v*v的行列式非0的Syndrome矩阵
     * @param v 矩阵的维数
     * @param p 公共参数
     * @param pc 预计算参数
     * @param indexSyndrome syndrome索引
     * @return 行列式非0的Syndrome矩阵的维数
     */
    private int lengthOfNonZeroMatrix(int v, parameters p, preCompute pc, int[] indexSyndrome){
        for(int i=v;i>=1;i--){
            boolean isZero = isZeroDetMatrix(p,pc,indexSyndrome,v);
            if(isZero) v--;
            else break;
        }
        return v;
    }

    /**
     * 寻找错误向量
     * @param syndromes syndrome
     * @param indexSyndromes syndrome的索引
     * @param v syndrome矩阵的纬度
     * @param p 公共参数
     * @param pc 预计算参数
     * @return 返回错误向量的索引
     */
    private List<Integer> findError(int[][] syndromes,int[] indexSyndromes,int v,parameters p,preCompute pc){
        List<Integer> err = new ArrayList<>();
        int sum = 0;
        for(int i=0;i<syndromes[0].length;i++){
            sum+=syndromes[0][i];
        }
        if((sum!=0)||(v!=1)){
            int[] gamma = invMatrixMultiplyC(p,pc,indexSyndromes,v);
            for(int i=0;i<p.getN();i++){
                int[][] equation = new int[gamma.length+1][pc.getAlpha().getValue()[0].length];
                //写入equation前gamma.length-1项
                for(int j=0;j<gamma.length;j++){
                    //如果为0则那一行直接为0,不需要额外处理
                    if(gamma[j]!=0){
                        int tIndex = Math.floorMod((i+1)*(gamma.length-j)+gamma[j]-1,p.getN());
                        equation[j] = pc.getAlpha().getValue()[tIndex];
                    }
                }
                //equation最后一项为1，即最后一行为[0,0,....,0,1]，长度为pc.getAlpha().getValue()[0]的长度
                equation[gamma.length][pc.getAlpha().getValue()[0].length-1] = 1;
                //对equation按列求和并模2
                int[] sumEquation = new int[equation[0].length];
                for(int j=0;j<equation[0].length;j++){
                    for (int[] ints : equation) {
                        sumEquation[j] += ints[j];
                    }
                    sumEquation[j] = sumEquation[j]%2;
                }
                int se = 0;
                for (int k : sumEquation) {
                    se += k;
                }
                if(se==0) err.add(i+1);
            }
        }
        return err;
    }

    /**
     * 得到正确的码字
     * @param codeword 接收的码字
     * @param err 错误的位置
     * @return 返回正确的码字
     */
    private int[] getCorrectCodeword(int[] codeword, List<Integer> err){
        int[] ans = Arrays.copyOf(codeword,codeword.length);
        for (Integer i : err) {
            ans[i - 1] = (ans[i - 1] + 1) % 2;
        }
        return ans;
    }

    /**
     * 求两个syndrome的差
     * @param syndrome1 第一个syndrome
     * @param syndrome2 第二个syndrome
     * @return 返回两个syndrome的差之后的syndrome
     */
    private int[][] diffSyndromes(int[][] syndrome1,int[][]syndrome2){
        int[][] diff = new int[syndrome1.length][syndrome1[0].length];
        for(int i=0;i<syndrome1.length;i++){
            for(int j=0;j<syndrome1[0].length;j++){
                diff[i][j] = (syndrome1[i][j] + syndrome2[i][j])%2;
            }
        }
        return diff;
    }

    /**
     * 得到错误向量
     * @param p 公共参数
     * @param err 错误的位置
     * @return 返回错误向量
     */
    private int[] getErrorVector(parameters p, List<Integer> err){
        int[] ans = new int[p.getN()];
        for (Integer i : err) {
            ans[i - 1] = (ans[i - 1] + 1) % 2;
        }
        return ans;
    }

    /**
     * 判断矩阵S的行列式是否为0
     * @param p 公共参数
     * @param pc 预计算参数
     * @param indexSyndrome indexSyndromes
     * @param v 构造S矩阵和C矩阵，v为S矩阵的行(列)数
     * @return 矩阵行列式为0则返回true，否则返回false
     */
    private boolean isZeroDetMatrix(parameters p, preCompute pc, int[] indexSyndrome, int v){
        //shadowS存储的是矩阵S中对应的特征(syndromes)的次数
        int[][] shadowS = new int[v][v];
        for(int i=0;i<v;i++){
            for(int j=0;j<v;j++){
                shadowS[i][j] = indexSyndrome[i+j];
            }
        }
        for(int i=0;i<v;i++){
            int ts1 = shadowS[i][i];
            boolean detS = true;
            if(ts1==0){//如果为0，则需要和不为0的行换位置
                for(int j=i;j<v;j++){//如果恰恰只有最后一行为零，则进入不到这个循环中
                    if(shadowS[j][i] != 0){//如果后面的行不为零，则交换两行的位置
                        int[] ts2 = shadowS[j];
                        shadowS[j] = shadowS[i];
                        shadowS[i] = ts2;
                        detS = false;
                    }
                }
                if(detS){//如果恰恰只有最后一行为零，则进入不到上面循环中，det此时为0
                    return true;
                }
            }
            ts1 = shadowS[i][i];//因为做了行交换，所以需要更新一下ts1
            for(int j=0;j<v;j++){//如果不为0，则首先把对角线上元素乘其逆，变成单位元
                if(shadowS[i][j]!=0){//由于0代表着0元，所以需要单独处理，否则就会被当成单位元处理了
                    shadowS[i][j] = Math.floorMod(shadowS[i][j]+(p.getN()-ts1),p.getN());
                    if(shadowS[i][j]==0) shadowS[i][j] = p.getN(); //这里用alpha^n当作1(单位元),用0来当作0(零元)
                }
            }
            for(int j=0;j<v;j++){//用做好变换的行来处理其他行，把其他行对应的位置变为0
                if((j!=i) && shadowS[j][i]!=0){//对等于0的行不需要处理
                    int ts3 = shadowS[j][i];//ts3就是一行需要乘的次数，由于shadow_s都是幂次，所以在后面是加法
                    int[] ts4 = new int[v];
                    for(int k=0;k<v;k++){//用ts4来接住行变换，然后与对应的行相减
                        if(shadowS[i][k]!=0){
                            ts4[k] = Math.floorMod(shadowS[i][k]+ts3,p.getN());//在这里幂次相加模之后得到新的幂次
                            if(ts4[k]==0) ts4[k] = p.getN();
                        }
                    }
                    for(int k=0;k<v;k++){//接下来是做好变换的行与另一行相减得到新的行
                        int[] ts5 = new int[p.getG().getDeg()];//由于0代表着0元，所以需要单独处理，否则就会被当成单位元处理了
                        if(shadowS[j][k]!=0){//对非0元我们可以读出其alpha值
                            ts5 = pc.getAlpha().getValue()[shadowS[j][k]-1];
                        }
                        int[] ts6 = new int[p.getG().getDeg()];//由于0代表着0元，所以需要单独处理，否则就会被当成单位元处理了
                        if(ts4[k]!=0){//对非0元我们可以读出其alpha值
                            ts6 = pc.getAlpha().getValue()[ts4[k]-1];
                        }
                        polynomial ts7 = new polynomial(ts5).add(new polynomial(ts6));
                        //把ts7从二进制转成10进制
                        int two = 1;
                        int dec7 = 0;
                        for(int l=ts7.getNums().length-1;l>=0;l--){
                            if(ts7.getNums()[l]==1) dec7 += two;
                            two *= 2;
                        }
                        //由于0代表着0元，所以需要单独处理，否则就会被当成单位元处理了
                        if(dec7==0){
                            ts4[k] = 0;
                        }else {
                            dec7 = Math.floorMod(dec7-1,p.getN());//反独取的时候需要-1并且模n，因为索引是从0开始的
                            ts4[k] = pc.getAlpha().getIndexes()[dec7];//在这里就被转成幂次了，赋值给ts4
                        }
                    }
                    shadowS[j] = ts4.clone();
                }
            }
        }
        //System.out.println(Arrays.deepToString(shadowS));
        return false;
    }

    /**
     * 判断矩阵S求逆后与c向量乘，直接对[S|C]使用S的求逆过程，即，A=inv(S)，则A[S|C]=[AS|AC]=[I|AC]=[I|inv(S)C]
     * @param p 公共参数
     * @param pc 预计算参数
     * @param indexSyndrome indexSyndromes
     * @param v 构造S矩阵和C矩阵，v为S矩阵的行(列)数
     * @return 返回S^{-1}*C的结果，如果返回全0的向量，则说明S不是可逆矩阵
     */
    private int[] invMatrixMultiplyC(parameters p, preCompute pc, int[] indexSyndrome, int v){
        int[] ans = new int[v];
        //shadowS存储的是矩阵S中对应的特征(syndromes)的次数
        int[][] shadowS = new int[v][v+1];
        for(int i=0;i<v;i++){
            for(int j=0;j<v;j++){
                shadowS[i][j] = indexSyndrome[i+j];
            }
            shadowS[i][v] = indexSyndrome[i+v];
        }
        for(int i=0;i<v;i++){
            int ts1 = shadowS[i][i];
            boolean detS = true;
            if(ts1==0){//如果为0，则需要和不为0的行换位置
                for(int j=i;j<v;j++){//如果恰恰只有最后一行为零，则进入不到这个循环中
                    if(shadowS[j][i] != 0){//如果后面的行不为零，则交换两行的位置
                        int[] ts2 = shadowS[j];
                        shadowS[j] = shadowS[i];
                        shadowS[i] = ts2;
                        detS = false;
                    }
                }
                if(detS){//如果恰恰只有最后一行为零，则进入不到上面循环中，det此时为0
                    return ans;
                }
            }
            ts1 = shadowS[i][i];//因为做了行交换，所以需要更新一下ts1
            for(int j=0;j<v+1;j++){//如果不为0，则首先把对角线上元素乘其逆，变成单位元
                if(shadowS[i][j]!=0){//由于0代表着0元，所以需要单独处理，否则就会被当成单位元处理了
                    shadowS[i][j] = Math.floorMod(shadowS[i][j]+(p.getN()-ts1),p.getN());
                    if(shadowS[i][j]==0) shadowS[i][j] = p.getN(); //这里用alpha^n当作1(单位元),用0来当作0(零元)
                }
            }
            for(int j=0;j<v;j++){//用做好变换的行来处理其他行，把其他行对应的位置变为0
                if((j!=i) && shadowS[j][i]!=0){//对等于0的行不需要处理
                    int ts3 = shadowS[j][i];//ts3就是一行需要乘的次数，由于shadow_s都是幂次，所以在后面是加法
                    int[] ts4 = new int[v+1];
                    for(int k=0;k<v+1;k++){//用ts4来接住行变换，然后与对应的行相减
                        if(shadowS[i][k]!=0){
                            ts4[k] = Math.floorMod(shadowS[i][k]+ts3,p.getN());//在这里幂次相加模之后得到新的幂次
                            if(ts4[k]==0) ts4[k] = p.getN();
                        }
                    }
                    for(int k=0;k<v+1;k++){//接下来是做好变换的行与另一行相减得到新的行
                        int[] ts5 = new int[p.getG().getDeg()];//由于0代表着0元，所以需要单独处理，否则就会被当成单位元处理了
                        if(shadowS[j][k]!=0){//对非0元我们可以读出其alpha值
                            ts5 = pc.getAlpha().getValue()[shadowS[j][k]-1];
                        }
                        int[] ts6 = new int[p.getG().getDeg()];//由于0代表着0元，所以需要单独处理，否则就会被当成单位元处理了
                        if(ts4[k]!=0){//对非0元我们可以读出其alpha值
                            ts6 = pc.getAlpha().getValue()[ts4[k]-1];
                        }
                        polynomial ts7 = new polynomial(ts5).add(new polynomial(ts6));
                        //把ts7从二进制转成10进制
                        int two = 1;
                        int dec7 = 0;
                        for(int l=ts7.getNums().length-1;l>=0;l--){
                            if(ts7.getNums()[l]==1) dec7 += two;
                            two *= 2;
                        }
                        //由于0代表着0元，所以需要单独处理，否则就会被当成单位元处理了
                        if(dec7==0){
                            ts4[k] = 0;
                        }else {
                            dec7 = Math.floorMod(dec7-1,p.getN());//反独取的时候需要-1并且模n，因为索引是从0开始的
                            ts4[k] = pc.getAlpha().getIndexes()[dec7];//在这里就被转成幂次了，赋值给ts4
                        }
                    }
                    shadowS[j] = ts4.clone();
                }
            }
        }
        for(int i=0;i<v;i++){
            ans[i] = shadowS[i][v];
        }
        return ans;
    }
}
